#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/3 20:59
# @USER    : Shengji He
# @File    : SetMatrixZeros.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

        Example 1:
            Input:
                [
                  [1,1,1],
                  [1,0,1],
                  [1,1,1]
                ]
            Output:
                [
                  [1,0,1],
                  [0,0,0],
                  [1,0,1]
                ]
        Example 2:
            Input:
                [
                  [0,1,2,0],
                  [3,4,5,2],
                  [1,3,1,5]
                ]
            Output:
                [
                  [0,0,0,0],
                  [0,4,5,0],
                  [0,3,1,0]
                ]
        Follow up:
            - A straight forward solution using O(mn) space is probably a bad idea.
            - A simple improvement uses O(m + n) space, but still not the best solution.
            - Could you devise a constant space solution?
        """
        rows = len(matrix)
        columns = len(matrix[0])
        rz, cz = set(), set()
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == 0:
                    rz.add(i)
                    cz.add(j)

        for i in range(rows):
            for j in range(columns):
                if i in rz or j in cz:
                    matrix[i][j] = 0


if __name__ == '__main__':
    S = Solution()
    matrix = [[0, 0, 0, 5], [4, 3, 1, 4], [0, 1, 1, 4], [1, 2, 1, 3], [0, 0, 1, 1]]
    # matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
    S.setZeroes(matrix)
    print(matrix)
    print('done')
